#include <iostream>
#include <string>
#include<queue>
using namespace std;

struct node{
    char value;
    node*leftc=NULL;
    node*rightc=NULL;
};

int search(string str,char ch){
    for(int i =0;i<str.length();++i){
        if(str[i]==ch)return i;
    }
            return -1;
}

node* createTreeByPreIn(string pre,string in){
    if(pre=="")return NULL;
    node *t=new node;
    if(pre.length()==1){
        t->value=pre[0];
//        cout<<t->value<<endl;
    }
    else{
        char root=pre[0];
        int index=search(in,root);
        node *left=createTreeByPreIn(pre.substr(1,index),in.substr(0,index-1));
        node *right=createTreeByPreIn(pre.substr(index+1,pre.length()-index-1),in.substr(index+1,in.length()-index-1));
        t->value=root;
//        cout<<index<<"\t"<<t->value<<endl;
        t->rightc=right;
        t->leftc=left;
    }
    return t;
}

node* createTreeByPostIn(string post,string in){
    if(post=="")return NULL;
    node*t=new node;
    if(post.length()==1)
        t->value=post[0];
    else{
        char root=post[post.length()-1];
        int index=search(in,root);
        node*left=createTreeByPostIn(post.substr(0,index),in.substr(0,index));
        node*right=createTreeByPostIn(post.substr(index,post.length()-1-index),in.substr(index+1));
        t->value=root;
        t->leftc=left;
        t->rightc=right;
    }
    return t;
}


void postTree(node*root){
    if(root!=NULL){
        postTree(root->leftc);
        postTree(root->rightc);
        cout<<root->value;
    }
}

void preTree(node*root){
    if(root!=NULL){
        cout<<root->value;
        preTree(root->leftc);
        preTree(root->rightc);
    }
}
void inTree(node*root){
    if(root!=NULL){
        inTree(root->leftc);
        cout<<root->value;
        inTree(root->rightc);
    }
}

void deleteNode(node*root){
    if(root!=NULL){
        deleteNode(root->leftc);
        deleteNode(root->rightc);
        delete root;
    }
}

int main()
{
    string pre="ABDFGCEH";
    string in="BFDGACEH";
    string post="FGDBHECA";

    cout<<"前序后续还原二叉树，中序遍历输出："<<endl;
    node*t=createTreeByPreIn(pre,in);
    postTree(t);
    cout<<endl;

/*    node**/ t=createTreeByPostIn(post,in);
    cout<<endl;
    cout<<"中序后续还原二叉树，前序遍历输出："<<endl;
    preTree(t);
    cout<<endl;

    deleteNode(t);
}
